package leetcode100

// TODO 动态规划 | 状态转移方程 [内卷] 【-】 不同的二叉搜索树
// TODO https://leetcode.cn/problems/unique-binary-search-trees/solution/shou-hua-tu-jie-san-chong-xie-fa-dp-di-gui-ji-yi-h/

func numTrees(n int) int {
	dp := make([]int, n+1)
	dp[0] = 1
	dp[1] = 1
	// 求 dp[i]
	for i := 2; i <= n; i++ {
		// j 为 0 - i-1
		for j := 0; j <= i-1; j++ {
			dp[i] += dp[j] * dp[i-j-1]
		}
	}
	return dp[n]
}
